\section{Partitioning}

Partition algorithms rearrange elements in the range based on a predicate, such that elements for which the predicate returns \cpp{true} precede elements for which the predicate returns \cpp{false}.

Partitioning comes up often when we need to group elements based on a particular property. You can also think of partitioning as equal to sorting if we would sort based on the values of a boolean property.

\subsection{\texorpdfstring{\cpp{std::partition}}{\texttt{std::partition}}}
\index{\cpp{std::partition}}

The \cpp{std::partition} algorithm provides the basic partitioning functionality, reordering elements based on a unary predicate. The algorithm returns the partition point, an iterator to the first element for which the predicate returned \cpp{false}.

\cppversions{\texttt{partition}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{forward\_range}}{\texttt{forward\_range}}{N/A}{\texttt{unary\_predicate}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/9P8eWKfsd}{\ExternalLink}}
\footnotesize Example of using \cpp{std::partition} to process exam results.
\tcblower
\cppfile{code_examples/algorithms/partition_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::stable_partition}}{\texttt{std::stable\_partition}}}
\index{\cpp{std::stable_partition}}

The \cpp{std::partition} algorithm is permitted to rearrange the elements with the only guarantee that elements for which the predicate evaluated to \cpp{true} will precede elements for which the predicate evaluated to \cpp{false}. This behaviour can be undesirable, for example, for UI elements.

The \cpp{std::stable_partition} algorithm adds the guarantee of preserving the relative order of elements in both partitions.

\cppversions{\texttt{stable\_partition}}{\CC98}{N/A}{\CC17}{\CC20}

\constraints{\texttt{bidirectional\_range}}{\texttt{bidirectional\_range}}{N/A}{\texttt{unary\_predicate}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/zjeczYqK8}{\ExternalLink}}
\footnotesize Example of using \cpp{std::stable_partition} to move selected items to the beginning of a list.
\tcblower
\cppfile{code_examples/algorithms/stable_partition_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::is_partitioned}}{\texttt{std::is\_partitioned}}}
\index{\cpp{std::is_partitioned}}

The \cpp{std::is_partitioned} algorithm is a linear check returning a boolean denoting whether the ranges elements are partitioned in regards to the predicate.

\cppversions{\texttt{is\_partitioned}}{\CC11}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{input\_range}}{\texttt{forward\_range}}{N/A}{\texttt{unary\_predicate}}

Note that a sorted range is always partitioned for any possible value (with a different partition point).

\begin{codebox}[]{\href{https://compiler-explorer.com/z/nKecEhs3b}{\ExternalLink}}
\footnotesize Example of using \cpp{std::is_partitioned}.
\tcblower
\cppfile{code_examples/algorithms/is_partitioned_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::partition_copy}}{\texttt{std::partition\_copy}}}
\index{\cpp{std::partition_copy}}

The \cpp{std::partition_copy} is a variant of \cpp{std::partition} that, instead of reordering elements, will output the partitioned elements to the two output ranges denoted by two iterators.

\cppversions{\texttt{partition\_copy}}{\CC11}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{input\_range -> (output\_iterator, output\_iterator)}}{\texttt{forward\_range -> (forward\_iterator, forward\_iterator)}}{N/A}{\texttt{unary\_predicate}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/nzrbczh4j}{\ExternalLink}}
\footnotesize Example of using \cpp{std::partition_copy} to copy even elements into one range and odd elements into another range.
\tcblower
\cppfile{code_examples/algorithms/partition_copy_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::nth_element}}{\texttt{std::nth\_element}}}
\index{\cpp{std::nth_element}}

The \cpp{nth_element} algorithm is a partitioning algorithm that ensures that the element in the nth position is the element that would be in this position if the range was sorted.

The nth element also partitions the range into $\texttt{[begin, nth)}$, $\texttt{[nth, end)}$ such that all elements preceding the nth element are less than or equal to the rest of the range. Alternatively, for any element $i \in \texttt{[begin, nth)}$ and $j \in \texttt{[nth, end)}$ it holds that $\neg (j < i)$.

\cppversions{\texttt{nth\_element}}{\CC98}{\CC20}{\CC17}{\CC20}

\constraints{\texttt{(random\_access\_range, random\_access\_iterator)}}{\texttt{(random\_access\_range, random\_access\_iterator)}}{\texttt{operator<}}{\texttt{strict\_weak\_ordering}}

Because of its selection/partitioning nature, \cpp{std::nth_element} offers a better theoretical complexity than \cpp{std::partial_sort} - $O(n)$ vs $O(n*logk)$.

However, note that the standard only mandates average $O(n)$ complexity, and \cpp{std::nth_element} implementations can have high overhead, so always test to determine which provides better performance for your use case.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/n7T3h5sM8}{\ExternalLink}}
\footnotesize Example of using \cpp{std::nth_element}.
\tcblower
\cppfile{code_examples/algorithms/nth_element_code.h}
\end{codebox}